– Para a ?K:
a) a + a = 1
b) a . a = 0
V.1 Principio de Dualidad
Establece que si una expresión es válida en el álgebra de boole, entonces su
expresión dual también lo es.
Determinamos la expresión dual remplazando los operadores + por · y viceversa
y todos los elementos 0 por 1 y viceversa.
Ejemplo:
a + (b · c) = 1, expresión su dual es a · (b + c) = 0
V.2 Teoremas
Teorema 1: Idempotencia: Tanto la suma como el producto de una variable
booleana consigo misma da como resultado la misma variable.
a) a + a = a
b) a · a = a
?
?
Demostración:
a+a=
(a + a) · 1 =
(a + a) · (a + a) =
a + a · a =
a+0=a
Teorema 2: Elemento neutro para + y ·
a) a + 1 = 1
b) a · 0 = 0
? Demostración:
a+1=
(a + 1) · 1 =
1 · (a + 1) =
(a + a) · (a + 1) =
a + a · 1 =
a + a = 1
Teorema 3: Involución: Una variable booleana negada dos veces, da
como resultado la misma variable:
?
a = a
? Demostración:
a+1=
a · 1 + 0 =
a · (a + a) + a · a =
a · a + a · a + a · a =
a · (a + a) = a
? Teorema 4 : Absorción
a) a + a · b = a
b) a · (a + b) = a
? Demostración:
a+a·b=
a·1+a·b=
a · (1 + b) =
a·1=a
?
Teorema 5:
a) a + a · b = a + b
b) a · ( a + b) = a · b
?
? Demostración :
a + a · b =
(a + a) · (a + b) =
1 · (a + b) =
(a + b) · 1 = a + b
? Teorema 7:
a) a · b + a · b · c = a · b + a · c
b) (a + b) · (a + b + c) = (a + b) ·(a + c)
? Demostración:
a·b+a·b·c=
a · (b + b · c) =
a · (b + c) = a · b + a · c
?
? Teorema 8: Teorema de Morgan:
a) a + b = a · b
b) a · b = a + b
? En general:
a + b + … + z = a · b · c · … · z
a · b · c · … · z = a + b + c + … + z
Demostración del Teorema de Morgan
x+y=
(a + b) + a · b =
(b + a) + a · b =
b + (a + a .b) =
b + (a + b) =
(a + b) + b =
a + (b + b) =
a+l=l
entonces :
x+y=1
resulta :
x = y => a + b = a + b
x·y=
(a + b) · (a · b) =
(a · b) · (a + b) =
(a · b) · a + (a · b) · b =
a · ( a · b) + b · (a · b ) =
(a · a) · b + a · (b · b) =
0 · b + a · 0 =
b · 0 + a · 0 =
0+0=0
entonces:
x·y=0
? Teorema 6 :
a) a · b + a · b = a
b) (a + b) · (a + b) = a
? Demostración:
a·b+a·b=
a · (b + b) =
a·1=a
x = a + b => x = a + b
sabemos:
x·x=o
x+x=l
asumimos :
x·y=O
x+y=l
entonces:
y=x
asumimos :
y = a · b
? Teorema 9: Consenso
a) a · b + a · c + b · c = a · b + a · c
b) (a + b) · (a + c) · (b + c) = (a + b) · (a + c)
? Demostración:
a · b + a · c + b · c =
a · b + a · c + 1 · b · c =
a · b + a · c + (a + a) · b · c =
a · b + a · c + a · b · c + a · b · c = a · b + a · c
VI Funciones de Conmutación
Sean x1, x2, … , xn símbolos llamados variables, cada uno representa un 0 o un 1,
definiremos f(x1, x2, … , xn) como una función de conmutación de x1, x2, … , xn f
puede tomar el valor de 0 ó 1 según los valores para x1, x2, … , xn; si existen n
variables (xi), entonces existe 2n formas de asignar los valores para x1, x2, … , xn y
como f tiene dos posibles valores, existen 22n diferentes funciones para n variables.
Ejemplos:
? n=0
f()=0,1
? n=1
f(x)=0 1,x,x
? n=2
f(x,y)= 0
,
x.y
,
x.y ,
x
x.y ,
x.y ,
x,
y ,
x.y+x.y,
x+y ,
x.y+x.y,
y,
x+y,
x+y
x+y
1
Representación de una función de Conmutación
? Tabla de Verdad:
Evaluamos todos los posibles valores de entrada de la función y los colocamos en
una forma ordenada de acuerdo al orden decimal.
Ejemplo:
a b
f(x, y) = x+y
a+b
a b
f(x, y) = x.y
a+b
0 0
0
0 0
0
0 1
1
0 1
0
1 0
1 1
1
1
1 0
1 1
0
1
Tabla de Verdad
? Describa una función de conmutación con 3 entradas a, b y c una salida z, que
es verdadera (1)cuando al menos 2 de sus entradas son verdaderas (1)
a
b
c
f
0
0
0
0
0
0
1
1
1
1
0
1
0
0
1
1
1
1
0
1
0
1
0
1
0
1
1
1
VI.1 Representación de una función de Conmutación
? Formas Algebraicas
– SOP (Suma de Productos):se construye al sumar(or)términos productos
(and).
Ejm: f(a, b, c, d) = a · b · c + b · d + a · c · d
– POS(Producto de sumas):se construye con el
producto (and)de términos suma (or).
*Ejemplo: f(a, b, c, d) = (a + b + c) · (a + d)
Formas Algebraicas:
a
b c
f
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
0
0
0
1
1
1
0
Representación de una función de Conmutación
? Formas Canónicas:
Son formas SOP y POS con características especiales. Existe una única forma
canónica para cada función de conmutación.
–
Minitérmino: es un término producto(and) para una función de n variables, en
donde cada una aparece bien sea complementada o sin complementar.
* ejm: f(a,b,c) m = a· b · c, a · b · c, a · b · c
–
Maxtérmino: es un término suma (or) para una
? Las variables que tiene 0
? Las variables que tiene 1
función de n variables, en donde cada una
aparece bien sea complementada o sin
complementar.
* ejemplo: f(a, b, c) M = (a + b + c), (a + b + c )
Formas Canónicas SOP
f (a,b,c) = a ·b ·c + a · b · c + a · b ·c
a · b · c
a·b·c
a
0
0
0
0
1
1
1
1
b
0
0
1
1
0
0
1
1
c
0
1
0
1
0
1
0
1
f
1
0
1
0
0
0
0
1
a+b+c
a+b+c
a+b+c
a
0
0
0
0
1
1
1
1
b
0
0
1
1
0
0
1
1
c
0
1
0
1
0
1
0
1
f
0
1
1
0
1
1
0
1
Representación de una función de
Conmutación
? Especificación decimal:
-SOP:
f(a, b, c) = a · b · c + a · b · c + a · b · c + a · b · c
f(a, b, c) = m2 · m3 · m6 · m7
f(a, b, c) = m(2,3, 6, 7)
– POS:
aparecen complementadas
Formas Canónicas POS
f (a, b, c) = (a + b + c) · (a + b + c) · (a + b + c)
Relación con la tabla de
verdad:
Cada mintérmino está
asociado con la línea de la
que:
? Las variables que tiene 1
no están complementadas
aparecen complementadas
Relación con la tabla de
verdad:
Cada maxtérmino está
asociado con la línea de la
que:
? Las variables que tiene 0
no están complementadas
?
f(a, b, c) = (a + b + c) · (a + b + c) · (a + b + c) · (a + b + c)
f(a, b, c) = M1 · M3 · M5 · M7
f(a, b, c) = M (1, 3, 5, 7)
?
Relación Mintérminos
Maxtérminos
?
?
?
mi = Mi
Mi = mi
F(a, b, c) =
m(2, 3, 6, 7) =
M(0, 1, 4, 5)
En
Deducción de Formas Canónicas
? Teorema 10: Teorema de desarrollo de Shannon.
a) f(x1, x2,…, xn) = x1 · f(1, x2,
, xn) + x1 · f(0, x2,
, xn)
b) f(x1, x2,…, xn) = [x1 + f(0,x2,
,xn)]·[x1 + f(1,x2,
,xn)]
Convertir a SOP Canónica
f(a, b, c) = a · b + a · c + a · c
= a · f(l, b, c) + a · f(0, b, c)
= a · (b + c) + a · c
= b · f(a, l, c) + b · (a, 0, c)
= b · (a + a · c) + b · (a · c + a · c)
= a · b + a · b · c + a · b · c + a · b ·c
= c · f(a, b, l) + c · (a, b, 0)
= c · (a · b + a · b + a · b) + c · (a · b + a · b)
= a · b · c + a · b · c + a · b · c + a · b · c + a · b ·c
= L m(1, 3, 4, 6, 7)
Convertir a SOP Canónica
T6: a · b + a · b = a
f(a, b, c) = a · b + a · c + a · c
a · b = a · b · c + a · b · c = m7+ m6
a · c = a · b · c + a · b · c = m6+ m4
a · c = a · b · c + a · b · c = m3+ m1
f(a, b, c) = m(1, 3, 4, 6, 7)
Convertir a POS Canónica
f(a, b, c) = a · (a + c)
= (a + b · b + c · c) · (a + b · b + c)
= ((a + b) · (a + b ) + c · c) · ((a + b) · (a + b ) + c)
= (a + b + c · c) · (a + b + c · c) · (a + b + c) · (a + b + c)
= (a + b + c) · (a + b + c) · (a + b + c)(a + b + ·c) · (a + b + c) · (a + b + c)
= M(0, 1, 2, 3)
VII Minimización
? ?general al minimizar un sistema digital para su implementación con
compuertas ofrece:
?
Menor costo, consumo de potencia, espacio físico, tiempo de respuesta.
? Técnicas:
? Minimización Algebraica
? Minimización a través de Mapas de Karnuagh,
? Minimización Tabular
~
~
~
Implementac
ión
minimizada:
Minimización Algebraica
? Usa los teoremas del álgebra de Boole, para minimizar la función.
? No existe una técnica o método que indique cuales teoremas usar, en general se
recomienda:
– Expresar la función en forma de SOP o POS.
– Utilizar el teorema 6, para eliminar variables, duplicando términos que puedan
agruparse,
-Aplicar la ley distributiva
Minimización Algebraica
Ejemplo: z = a · b · c + a · b · (a · c)
Paso1:
Z = a · b · c + a · b ·(a + c)
Z=a·b·c+a·b+a·b·c
Paso 2:
Z=a·b·c+a·b·c+a·b·c
Z=a·b·c+a·b+a·b·c
Z = a · c · (b + b) + a · b · (1 + c)
Z=a·c+·a·b
Paso 3:
Z = a · (c + b)
Minimización Algebraica
Implementación original:
A
B
C
A
B
Z
A
C
A
B
C
Minimización por Mapas de Karnaugh
? Un mapa de Karnaugh es una representación gráfica de la tabla de verdad de
una función de conmutación.
? Para 2 variables:
Z
? Para 3 variables
? Para 4 variables
Minimización por mapas de Karnaugh
? Coloque 1s en las celdas correspondientes a los mintérminos de la función.
? Agrupe en un elipse lo mas grande posible, en conjuntos rectangulares de 1s,
– # de 1s en cada conjuntos debe ser potencia de 2,
– Se permite cursar elipses.
? El térmico producto resultante tendrá:
-Si la variable es 1 => incluya la variable,
– Si la variable es 0 => incluya la variable complementada
– Si la variable es tanto 0 y 1 => no incluya la variable.
? Las elipses correspondientes a los términos productos se llaman implicantes
primos.
?
Ejemplos
Minimización por mapas de Karnaugh
Minimización por mapas de Karnaugh
Minimización por mapas de Karnaug
Suma total: Suma de los implicantes primos
Minimización por mapas de Karnaugh
? Celdas 1 distinguidas: celdas 1 que están cubiertas por un único implicante
primo.
? Implicante primo esencial (IPE): implicante que contenga al menos una celda 1
distinguida.
? Suma mínima: Suma de los IPE.
f(w,x,y,z) = x·y·z + x·z + w·x +w·z
f(w,x,y,z) = w + x · z
F = X·Y + X·Z + W·X
Minimización por mapas de Karnaugh
2,3,4,5,6,7,11,13,15)
Minimización por mapas de Karnaugh
? Implicantes primos esenciales secundarios (IPES),
? Suma Mínima = IPE + IPES
W·Y + W·X + X·Z + Y·Z)
0,1,2,3,4,5,7,14,15)
Minimización por mapas de Karnaugh
2,6,7,9,13,15)
W·Y·Z + W·Y·Z + X·Y·Z)
Minimizaciones por mapas de Karnaugh
Expansión con Multiplexores
Funciones con Multiplexores
X·Y·Z
W·Y·Z
W·X·Z
W·Y·Z
W·X·Z
X·Y·Z
Página anterior | Volver al principio del trabajo | Página siguiente |